Advanced data structure/ Consider the strange case of PhileasFogg (Around the World in 80 Days by Jules Verne)
Uses: Graphs, Shortest Path, Symbol Table
Overview: Consider the strange case of PhileasFogg (Around the World in 80 Days by Jules Verne). He made a bet that by using available transportation, he could travel from London around the world and return to London in 80 days or less (This transpired in the 19th century). Your task to is to write a program to plan his route. The input will consist of a list of pairs of cities, a form of transportation between them, and the travel time. In addition, if the trip between the cities crosses an ocean, the name of the ocean will be included. Your program must find the shortest route around the world, starting at London and returning to London which crosses the Atlantic and Pacific oceans.
Input: The input will consist of a series of lines. Each line contains the name of two cities, a form of transportation between them, the travel time (in hours), and if the trip between cities crosses an ocean, the name of the ocean, in this order. Each line will contain either four or five fields, separated by at commas. For example, the input could look like:
London,Dover,train,3
Dover,Calais,ferry,3
Calais,Paris,train,2
Calais,Frankfurt,train,8
Paris,Istanbul,train,78
Paris,Geneva,train,10
Paris,Geneva,balloon,9
Istanbul,Tehran,camel,40
Tehran,Bombay,train,30
Bombay,Shanghai,train,60
Shanghai,Honolulu,steamship,390,Pacific
Shanghai,San Francisco,steamship,450,Pacific
Honolulu,San Francisco,steamship,70
San Francisco,New York,train,250
New York,London,clippership,209,Atlantic
All names (cities, oceans, and modes of transportation) will be strings. They may contain spaces. All times are integers. Your program should read the input from standard input and write to standard output. The input is terminated by the end of input (ctrl-Z or ctrl-D) as usual.
There may be more than one form of transportation between a pair of cities, e.g., balloon and train between Paris and Geneva. For the base problem, each line indicates transportation in both directions (but see the extra-credit problem below.) That is, if the input includes the line London,Dover,3,train, that implies that there is also a link from Dover to London by train which takes 3 hours. Cities in mid-ocean, e.g., Honolulu, are consider to be part of the nearest continent, so that an ocean is only crossed once when traveling through such a city, e.g., traveling from Shanghai to Honolulu is considered crossing the Pacific, but not from Honolulu to San Francisco. This will be reflected in the input.?Output: Your output should consist of the fastest time to go around the globe (in hours) followed by the list of cities and the mode of transportation taken between the cities. The route must cross both the Atlantic and Pacific Oceans.?Sample Output:
Shortest time = 1125
London,Dover,3,train
Dover,Calais,3,ferry
Calais,Paris,2,train
Paris,Istanbul,78,train
Istanbul,Tehran,40,camel
Tehran,Bombay,30,train
Bombay,Shanghai,60,train
Shanghai,San Francisco,450,steamship,Pacific
San Francisco,New York,250,train
New York,London,209,clippership,Atlantic

Extra Credit (10 points): For extra-credit, assume that all the links in the input are one direction. That is, the line London,Dover,3,train does not imply that there is a link from Dover to London. That link would have to be listed separately in the file. The shortest route may go from east to west, or it may go from west to east. The program should be sure to check that.
Sources: You may use only code from class or from the book (or your own code, of course,) and you may use the HashMap API.

Advanced data structure/ Consider the strange case of PhileasFogg (Around the World in 80 Days by Jules Verne)
Uses: Graphs, Shortest Path, Symbol Table
Overview: Consider the strange case of PhileasFogg (Around the World in 80 Days by Jules Verne). He made a bet that by using available transportation, he could travel from London around the world and return to London in 80 days or less (This transpired in the 19th century). Your task to is to write a program to plan his route. The input will consist of a list of pairs of cities, a form of transportation between them, and the travel time. In addition, if the trip between the cities crosses an ocean, the name of the ocean will be included. Your program must find the shortest route around the world, starting at London and returning to London which crosses the Atlantic and Pacific oceans.
Input: The input will consist of a series of lines. Each line contains the name of two cities, a form of transportation between them, the travel time (in hours), and if the trip between cities crosses an ocean, the name of the ocean, in this order. Each line will contain either four or five fields, separated by at commas. For example, the input could look like:
London,Dover,train,3
Dover,Calais,ferry,3
Calais,Paris,train,2
Calais,Frankfurt,train,8
Paris,Istanbul,train,78
Paris,Geneva,train,10
Paris,Geneva,balloon,9
Istanbul,Tehran,camel,40
Tehran,Bombay,train,30
Bombay,Shanghai,train,60
Shanghai,Honolulu,steamship,390,Pacific
Shanghai,San Francisco,steamship,450,Pacific
Honolulu,San Francisco,steamship,70
San Francisco,New York,train,250
New York,London,clippership,209,Atlantic
All names (cities, oceans, and modes of transportation) will be strings. They may contain spaces. All times are integers. Your program should read the input from standard input and write to standard output. The input is terminated by the end of input (ctrl-Z or ctrl-D) as usual.
There may be more than one form of transportation between a pair of cities, e.g., balloon and train between Paris and Geneva. For the base problem, each line indicates transportation in both directions (but see the extra-credit problem below.) That is, if the input includes the line London,Dover,3,train, that implies that there is also a link from Dover to London by train which takes 3 hours. Cities in mid-ocean, e.g., Honolulu, are consider to be part of the nearest continent, so that an ocean is only crossed once when traveling through such a city, e.g., traveling from Shanghai to Honolulu is considered crossing the Pacific, but not from Honolulu to San Francisco. This will be reflected in the input.?Output: Your output should consist of the fastest time to go around the globe (in hours) followed by the list of cities and the mode of transportation taken between the cities. The route must cross both the Atlantic and Pacific Oceans.?Sample Output:
Shortest time = 1125
London,Dover,3,train
Dover,Calais,3,ferry
Calais,Paris,2,train
Paris,Istanbul,78,train
Istanbul,Tehran,40,camel
Tehran,Bombay,30,train
Bombay,Shanghai,60,train
Shanghai,San Francisco,450,steamship,Pacific
San Francisco,New York,250,train
New York,London,209,clippership,Atlantic

Extra Credit (10 points): For extra-credit, assume that all the links in the input are one direction. That is, the line London,Dover,3,train does not imply that there is a link from Dover to London. That link would have to be listed separately in the file. The shortest route may go from east to west, or it may go from west to east. The program should be sure to check that.
Sources: You may use only code from class or from the book (or your own code, of course,) and you may use the HashMap API.